public class GetLongestPalindrome {
    public int getLongestPalindrome (String A) {
        // write code here
        if (A.length() == 0) {
            return 0;
        }
        char[] c = A.toCharArray();
        // dp[i][j]表示[i,j]之间的字符串是否为回文串
        boolean[][] dp = new boolean[c.length][c.length];
        // 状态转移方程：需要遍历第i个元素之前的元素是否可以和第i个位置形成回文串
        // 如果c[i] == c[j] && dp[j+1][i-1]，那么dp[i][j] = true
        // 所以填表顺序为从上往下、从右往左
        int ret = 1;
        for (int i = 0; i < c.length; i++) {
            for (int j = i; j >= 0; j--) {
                if (i == j || (c[i] == c[j] && ((j+1 > i-1) || dp[j+1][i-1]))) {
                    dp[j][i] = true;
                    ret = Math.max(ret, i-j+1);
                }
            }
        }
        return ret;
    }

    public static void main(String[] args) {
        System.out.println(new GetLongestPalindrome().getLongestPalindrome("baabccc"));
    }
}
